/*
 * A subclass of List with a built-in sorting capability. The ShellSort
 * code from the example program "SortingInAction" is used here, modified
 * slightly to work closely with the List object's data representation, i.e.
 * the array of objects pointed to by 'dataPtr'.
 *
 * The user of this class must set the SortingList's delegate to an object
 * which responds to the 'lessThan:(int)position1 :(int)position2' method,
 * which returns YES if object1 should be deemed to be "less than" object2
 * in a way that makes sense to the caller.
 *
 * Written by Rich Plevin, 24 Jun 92.
 *
 * This code may be freely used, copied and modified. The author disclaims
 * any warranty of any kind, expressed or implied, as to its fitness for any
 * particular use.
 * 
 * 8/18/92 - More general structure implemented (can set sort, comparison, and
 * 	value methods.  (value method returns the value for sorted key).  added
 *	insertion method which inserts object in order.  added sort flag and
 *	autosort feature.
 *
 * 8/19/92 - Added mergeList method and overrode indexOf to use binary search
 *
 * For legal stuff see the file COPYRIGHT
 */
#include "SortList.h"

#define STRIDE_FACTOR 3 // good value for stride factor is not well-understood
// 3 is a fairly good choice (Sedgewick)

@implementation SortList

- _updateChain
{
    if (!delegate) {
  	compObject = self;
  	if ([self respondsTo:compareMethod]) {
	    compMethod = compareMethod;
	}
	else {
	    compMethod = @selector(compare::);
	}
    }
    else {
	if ([delegate respondsTo:compareMethod]) {
	    compObject = delegate;
	    compMethod = compareMethod;
	}
	else if ([delegate respondsTo:@selector(compare::)]) {
	    compObject = delegate;
	    compMethod = @selector(compare::);
	}
	else if ([self respondsTo:compareMethod]) {
	    compObject = self;
	    compMethod = compareMethod;
	}
	else {
	    compObject = self;
	    compMethod = @selector(compare::);
	}
    }
    return self;
}

- initCount:(unsigned int)numSlots
{
    [super initCount:numSlots];
    compareMethod = @selector(compare::);
    compMethod = @selector(compare::);
    sortMethod = @selector(shellsort);
    compObject = self;
    sorted = NO;
    autoSort = NO;
    return self;
}

- (unsigned int)indexOf:anObject
/* overridden to use binary search.  assumes that object used for search and
 * object in list return the same key value 
 */
{
    int	index1 = 0, index2 = numElements - 1, mid, mark, val;
    
    if (anObject == nil)
	return NX_NOT_IN_LIST;

    if (sorted == NO)
	return [super indexOf:anObject];
    
    mid = (index2 + index1)/2;
    
    while (mid > index1) {
	if (anObject == dataPtr[mid])
	    return mid;
	if ((val = (int)[compObject perform:compMethod with:anObject
		     with:dataPtr[mid]]) < 0) {
	    index2 = mid;
	}
	else if (val == 0) {
	    mark = mid;
	    while (val == 0) {
		if (anObject == dataPtr[mark]) {
		    return mark;
		}
		mark--;
		val = (int)[compObject perform:compMethod with:anObject
			with:dataPtr[mark]];
	    }
	    mark = mid + 1;
	    while (val == 0) {
		if (anObject == dataPtr[mark]) {
		    return mark;
		}
		mark++;
		val = (int)[compObject perform:compMethod with:anObject
			with:dataPtr[mark]];
	    }
	    return NX_NOT_IN_LIST;
	}
	else {
	    index1 = mid;
	}
  	mid = (index2 + index1)/2;
    }
    if (anObject == dataPtr[index1]) {
  	return index1;
    }
    if (anObject == dataPtr[index2]) {
	return index2;
    }
    return NX_NOT_IN_LIST;
}

- addObject:anObject
{
    if (anObject == nil) return nil;
    [super addObject:anObject];
    [self update];
    return self;
}

- addObjectIfAbsent:anObject
{
    if (anObject == nil) return nil;
    [super addObjectIfAbsent:anObject];
    [self update];
    return self;
}

- insertObject:anObject at:(unsigned int)index
{
    id	returnObj;
    
    if (returnObj = [super insertObject:anObject at:index])
  	[self update];
    return returnObj;
}

- replaceObject:anObject with:newObject
{
    id	returnObj;
    
    if (returnObj = [super replaceObject:anObject with:newObject])
  	[self update];
    return returnObj;
}

- replaceObjectAt:(unsigned int)index with:newObject;
{
    id	returnObj;
    
    if (returnObj = [super replaceObjectAt:index with:newObject])
  	[self update];
    return returnObj;
}

- update
/* sorts list if autoSort is enabled, otherwise just sets the sorted flag
 * to NO.
 */
{
    if (autoSort)
  	[self sort];
    else
  	sorted = NO;
    return self;
}

- (BOOL)isSorted
{
    return sorted;
}

- setAutoSort:(BOOL)sortFlag
{
    autoSort = sortFlag;
    return self;
}

- (BOOL)doesAutoSort
{
    return autoSort;
}

- setDelegate:obj
{
    delegate = obj;
    [self _updateChain];
    return self;
}

- delegate
{
    return delegate;
}

- useSortMethod:(SEL)method
/* sort method can be defined in a subclass or in a delegate(??).  when -sort
 * is called, the SortList first checks the delegate then itself.  If neither
 * can respond, then a default(shellsort) is used.
 */
{
    sortMethod = method;
    return self;
}

- (SEL)sortMethod
{
    return sortMethod;
}

- useComparisonMethod:(SEL)method
/* sets the method used to compare the objects.  Overrides SortList's and
 * delegate's -compare:: methods.  Note that the compare method can, and in
 * most cases should, use the set valueMethod, if any were set.
 */
{
    compareMethod = method;
    [self _updateChain];
    
    return self;
}

- (SEL)comparisonMethod
{
    return compareMethod;
}

- useValueMethod:(SEL)method
/* sets method used to get value for sort key from objects. */
{
    valueMethod = method;
    return self;
}

- (SEL)valueMethod
{
    return valueMethod;
}

- sort
/* the chain goes something like this: delegate:sortMethod, self:sortMethod,
 * self:shellsort (default).
 */
{
    if (!delegate) {
  	if ([self respondsTo:sortMethod])
	    [self perform:sortMethod with:self];
	else	[self shellsort];
    }
    else {
  	if ([delegate respondsTo:sortMethod])
	    [delegate perform:sortMethod with:self];
	else if ([self respondsTo:sortMethod]) {
	    [self perform:sortMethod with:self];
	}
	else	[self shellsort];
    }
    sorted = YES;
    return self;
}

- insertObject:anObject
/* Inserts object into list in sorted order. if the list is not sorted, the
 * list sorts itself regardless of whether autosort is enabled.
 */
{
    int	index1 = 0, index2 = numElements - 1, mid, val;
    
    if (!sorted)
	[self sort];
    if (anObject == nil)
	return nil;
    mid = (index2 + index1)/2;

    if ([self count] == 0) {
	[self insertObject:anObject at:0];
	return self;
    }
	
    while (mid > index1) {
	if (anObject == dataPtr[mid])
	    return self;
	if ((val = (int)[compObject perform:compMethod with:anObject
		     with:dataPtr[mid]]) < 0) {
	    index2 = mid;
	} else if (val == 0) {
	    [self insertObject:anObject at:mid + 1];
	    return self;
	} else {
	    index1 = mid;
	}
  	mid = (index2 + index1)/2;
    } if ((val = (int)[compObject perform:compMethod with:anObject
		 with:dataPtr[index1]]) < 0) {
	[self insertObject:anObject at:index1];
    } else if ((val = (int)[compObject perform:compMethod with:anObject
		      with:dataPtr[index2]]) > 0) {
	[self insertObject:anObject at:index2 + 1];
    } else {
	[self insertObject:anObject at:index1 + 1];
    }
    sorted = YES;
    return self;
}

- mergeList:otherList
/* merges otherList into the list, the new list is sorted. */
{
    int i, j, val, ocount;
    BOOL otherSorted, isSortList;
    
    if (![otherList isKindOf:[List class]]) {
	return nil;
    }
    if ([otherList respondsTo:@selector(isSorted)] &&
  	[otherList respondsTo:@selector(sort)]) {
	isSortList = YES;
  	otherSorted = [otherList isSorted];
    }
    else {
  	otherSorted = NO;
	isSortList = NO;
    }
    
    ocount = [otherList count];
    i = j = 0;
    if (!otherSorted && sorted) {
	for (i = 0; i < ocount; i++) {
	    [self insertObject:[otherList objectAt:i]];
	}
    }
    else if (otherSorted && sorted) {
	while (j < ocount) {
	    while ((val = (int)[compObject perform:compMethod
			    with:dataPtr[i]
			    with:[otherList objectAt:j]]) < 0) {
		i++;
		if (i >= numElements) {
		    i = numElements - 1;
		}
	    }
	    [self insertObject:[otherList objectAt:j] at:i];
	    j++;
  	}
    }
    else if (!otherSorted && !sorted) {
	[self appendList:otherList];
	[self sort];
    }
    
    return self;
}

- (unsigned int)indexOfObjectWithKey:proxy
{
    int	index1 = 0, index2 = numElements - 1, mid, mark, val;
    
    if (proxy == nil || [self count] == 0)
	return NX_NOT_IN_LIST;

    if (sorted == NO) {
	[self sort];
    }
//	return [super indexOf:anObject];
    
    mid = (index2 + index1)/2;
    
    while (mid > index1) {
	if ((val = (int)[compObject perform:compMethod with:proxy
		     with:dataPtr[mid]]) < 0) {
	    index2 = mid;
	}
	else if (val == 0) {
	    mark = mid;
	    while (val == 0) {
		mark--;
		val = (int)[compObject perform:compMethod with:proxy
			with:dataPtr[mark]];
	    }
	    return mark + 1;
	}
	else {
	    index1 = mid;
	}
  	mid = (index2 + index1)/2;
    }
    if (((int)[compObject perform:compMethod with:proxy
		with:dataPtr[index1]]) == 0) {
  	return index1;
    }
    if (((int)[compObject perform:compMethod with:proxy
		with:dataPtr[index2]]) == 0) {
	return index2;
    }
    return NX_NOT_IN_LIST;
}


/*
 * This code was extracted from the /NextDeveloper/Examples/SortingInAction program.
 * The original author's comment:
 *
 *	Because Shellsort is a variation on Insertion Sort, it has the same 
 *	inconsistency that I noted in the InsertionSort class.  Notice where I 
 *	subtract a move to compensate for calling a swap for visual purposes.
 *
 *	Author: Julie Zelenski, NeXT Developer Support
 *	You may freely copy, distribute and reuse the code in this example.  
 *	NeXT disclaims any warranty of any kind, expressed or implied, as to 
 *	its fitness for any particular use.
 *
 * [This sounds like there is unnecessary work happening in this routine, but I
 * didn't dig into it enough to figure out what to change - rjp]
 *
 * Depending on what methods are set (and whether a delegate is set), the
 * comparison method will vary.  The chain of precedence is:
 *	delegate:comparisonMethod, delegate:compare::, self:comparisonMethod,
 *	self:compare::.
 */	
- shellsort
{
    int c, d, stride;
    BOOL found;
    
    stride = 1;
    while (stride <= numElements)
	stride = stride * STRIDE_FACTOR + 1;
    
    while (stride > STRIDE_FACTOR - 1 ) {
	/* loop to sort for each value of stride */
	stride = stride / STRIDE_FACTOR;
	
	for (c = stride; c < numElements; c++) {
	    found = NO;
	    d = c - stride; 
	    
	    while ( d >= 0 && !found ) {
		/* move to left until correct place */
		int target = d + stride ;
		
		if ((int)[compObject perform:compMethod
		      with:dataPtr[target]
		      with:dataPtr[d]] < 0) {
		    id tmp = dataPtr[target]; 	/* swap the elements */
		    dataPtr[target] = dataPtr[d];
		    dataPtr[d] = tmp ;
		    d -= stride;		/* jump by stride factor */
		} else
		    found = YES;
	    }
	}
    }
    return self;
}

- (int)compare:object1 :object2
{
    if ([object1 respondsTo:valueMethod] &&
    	[object2 respondsTo:valueMethod]) {
    	return [object1 perform:valueMethod] - 
	    [object2 perform:valueMethod];
    }
    else
  	return ((int)object1) - ((int)object2);
}

@end

@implementation SortingListDelegate
/*
 * Dummy delegated method
 */
- (int)compare:object1 :object2
{
    return 0;
}

- sort:aList
{
    [aList shellsort];
    return self;
}
@end

